#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;

//struct compare_iter_val
//{
//    bool operator()(map<string, int>::iterator l, map<string, int>::iterator r)
//    {
//        return l->second > r->second;
//    }
//};
//
//class Solution
//{
//public:
//    vector<string> topKFrequent(vector<string>& words, int k)
//    {
//        //用map进行统计
//        map<string, int> countMap;
//        for (auto& str : words)
//        {
//            countMap[str]++;
//        }
//        //将map中节点的迭代器放入vector并进行sort排序
//        vector<map<string, int>::iterator> v;
//        map<string, int>::iterator begin = countMap.begin();
//        while (begin != countMap.end())
//        {
//            v.push_back(begin);
//            begin++;
//        }
//        //排序
//        sort(v.begin(), v.end(), compare_iter_val());
//        //将前k个高频单词插入，并返回
//        vector<string> vs;
//        for (int i = 0; i < k; i++)
//        {
//            vs.push_back(v[i]->first);
//        }
//        return vs;
//    }
//};

class Solution
{
public:
    vector<string> topKFrequent(vector<string>& words, int k)
    {
        //用map进行统计
        map<string, int> countMap;
        for (auto& str : words)
        {
            countMap[str]++;
        }

        multimap<int, string, greater<int>> sortMap;
        for(auto& kv : countMap)
        {
            sortMap.insert(make_pair(kv.second, kv.first));
        }

        vector<string> v;
        int i = 0;
        for(auto& kv : sortMap)
        {
            if(i >= k)
            {
                break;
            }
            v.push_back(kv.second);
            i++;
        }
        return v;
    }
};

int main()
{
    vector<string> words = { "i", "love", "leetcode", "i", "love", "coding" };
    Solution s;
    s.topKFrequent(words, 2);
	return 0;
}